package com.tgy.leetcode;

/**
 * @Author: tgy
 * @Date: 12/26/20 4:24 PM
 *
 *   单链表可能有环， 也可能无环。 给定两个单链表的头节点 head1和head2， 这两个链表可能相交， 也可能不相交。 请实现一个函数， 如果两个链表相交， 请返回相交的第一个节点； 如果不相交， 返回null 即可。
 *
 */
public class 判断两个链表是否相交 {


    public ListNode twoLinkedListIntersection(ListNode headOne, ListNode headTwo) {

        if (headOne == null || headTwo == null) {

            return null;
        }

        ListNode cycleHeadOne = cycleFirstNode(headOne);
        ListNode cycleHeadTwo = cycleFirstNode(headTwo);

        /**
         * 一条链表有环，一条没有环，这两个链表不可能相交
         */
        if ((cycleHeadOne == null && cycleHeadTwo != null) || (cycleHeadOne != null && cycleHeadTwo == null)) {

            return null;
        }

        if (cycleHeadOne != null && cycleHeadOne != null) {

            if (cycleHeadOne == cycleHeadTwo) {

                /**
                 *
                 * 第一种
                 *  \ /
                 *  \/_ _
                 *  /    \
                 *  \_ _ /
                 *
                 *  第二种
                 *  \ /
                 *  \/
                 *  \_ _
                 *  /    \
                 *  \_ _ /
                 *
                 *
                 */

                // 一定有相交点
                ListNode tmp = cycleHeadOne.next;
                cycleHeadOne.next = null;
                ListNode intersectionNode = noCycleIntersectionNode(headOne, headTwo);
                cycleHeadOne.next = tmp;
                return intersectionNode;
            }else {

                /**
                 * 第一种情况
                 *  \    /
                 *  \_ _/
                 *  /   \
                 *  \__/
                 *
                 *  第二种情况
                 *  \
                 *  \_ _
                 *  /   \
                 *  \__/
                 *       /
                 *   _ _/
                 *  /   \
                 *  \__/
                 *
                 */

                ListNode tmp = cycleHeadOne;

                while (true) {

                    tmp = tmp.next;

                    if (tmp == cycleHeadOne) {

                        break;
                    }

                    if (tmp == cycleHeadTwo) {

                        return cycleHeadTwo;
                    }
                }

                return null;
            }
        }else {

            /**
             *
             * 两条链表都没有环，获取相交点
             */
            return noCycleIntersectionNode(headOne,headTwo);
        }
    }


    private ListNode noCycleIntersectionNode(ListNode headOne,ListNode headTwo) {

        ListNode tmpOne = headOne,tmpTwo = headTwo;

        /**
         * tmpOne == twpTwo 同时 等于 null
         * tmpOne == twpTwo 两个值不等于null
         */
        while (tmpOne != tmpTwo) {

            tmpOne = tmpOne == null? headTwo:tmpOne.next;
            tmpTwo = tmpTwo == null? headOne:tmpTwo.next;

        }

        return tmpOne;
    }

    /**
     * 获取链表是否有环，如果有获取第一个入环节点，没有返回null
     * @param head
     * @return
     */
    private ListNode cycleFirstNode(ListNode head) {

        if (head == null || head.next == null) {

            return null;
        }

        /**
         * head ,fast 起点一致
         */
        ListNode slow = head,fast = head;
        boolean flag = false;
        while (fast != null && fast.next != null) {

            slow = slow.next;
            fast = fast.next.next;

            if (slow == fast) {

                flag = true;
                break;
            }
        }

        if (!flag) {

            return null;
        }

        fast = head;

        while (fast != slow) {

            fast = fast.next;
            slow = slow.next;
        }

        return fast;
    }

}
